package algorithm_demo.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 316. 去除重复字母
 * <a href="https://leetcode.cn/problems/remove-duplicate-letters/">316. 去除重复字母</a>
 *
 * @author Api
 * @date 2023/5/10 21:22
 */
public class Problem_316_RemoveDuplicateLetters {
    //要求1：要去重
    //要求2：去重字符串中的字符顺序不能打乱s中字符出现的相对顺序
    //要求3：在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果
    public static String removeDuplicateLetters(String s) {
        // 存放去重的结果
        Deque<Character> stack = new ArrayDeque<>();
        //维护一个计数器记录字符串中字符的数量
        //因为输入为ASCII字符，大小256够用了
        int[] count = new int[256];
        for(int i = 0; i< s.length();i++){
            count[s.charAt(i)]++;
        }
        boolean[] inStack = new boolean[256];
        for(char c : s.toCharArray()){
            //每遍历过一个字符，都将对应的计数减1
            count[c]--;
            if(inStack[c]){
                continue;
            }
            while(!stack.isEmpty() && stack.peek() > c){
                //若之后不存在栈顶元素了，则停止pop
                if (count[stack.peek()] == 0){
                    break;
                }
                //若之后还有，则可以继续pop
                inStack[stack.pop()] = false;
            }
            stack.push(c);
            inStack[c] = true;
        }
        StringBuilder ans = new StringBuilder();
        while(!stack.isEmpty()){
            ans.append(stack.pollLast());
        }
        return ans.toString();
    }

    public static void main(String[] args) {
        removeDuplicateLetters("bcabc");
    }
}
